// #include<bits/stdc++.h> // 万能头文件

#include<iostream>

#include<algorithm>

#include<vector>
#include<list>


using namespace std;







template <typename Iterator>
void RandomShuffle(Iterator start,Iterator end)
{
    if (start == end)
        return;
    for(auto i = start + 1 ; i != end; i++)
    {
        auto j = start + rand%((i - start ) + 1);
        if(i != j)
        {
            std::swap(*i,*j);
        }
    }    
}










int main()
{
    // vector<int> v = {1,2,2,4,5,2,1};

    // for_each(v.begin(),v.begin()+2,[](int a){cout<<a<<" ";});

    // cout<<endl;




    // cout<<count(v.begin(),v.begin()+6,2)<<endl;  //可以快速统计出，在一个数列中 有多少个符合条件的数

    // cout<<count_if(v.begin(),v.begin()+4,[](int a){return a% 2 != 0;});






    // cout<<*min_element(v.begin(),v.begin()+4)<<endl;
    // //min_element 返回值是迭代器

    // cout<<*max_element(v.begin(),v.begin()+4)<<endl;

    // 最大值这个和最小值基本一致 
    


    // //find 是返回等于某个值的第一个元素
    // auto ite = find(v.begin(),v.end(),3);
    // //找不到就返回end 迭代器
    // if(ite != v.end())
    // {
    //     cout<<*ite<<endl;
    // }

    
    // auto ite = find_if(v.begin(),v.end(),[](int a){return a%2 != 0 && a>3;});
    // //找不到就返回end 迭代器
    // if(ite != v.end())
    // {
    //     cout<<*ite<<endl;
    // }


    // auto ite = search_n(v.begin(),v.end(),2,2);//找到的话 返回值

    // cout<<*ite<<endl;

    // vector<int> v ={1,2,3,3,3,4,5};
    
    // vector<int> v2 ={2,3,3};
    
    // //在前一个区间 中找后一个区间  返回找到的在第一个区间的迭代器
    // auto ite = search(v.begin(),v.end(),v2.begin(),v2.end());
    
    // cout<< *ite <<endl;
    

    // auto ite = find_end(v.begin(),v.end(),v2.begin(),v2.end());

    // cout<< *ite <<endl;

    //遍历第一个区间，找到一个元素 存在于 第二个区间，返回第一个存在于第二个区间中的元素的迭代器，否则返回 end迭代器
    // auto ite = find_first_of(v.begin(),v.end(),v2.begin(),v2.end());
    // cout<< *ite <<endl;
    // return 0;

    //找一个区间内 连续两个相等的元素
    // auto ite = adjacent_find(v.begin(),v.end());

    // cout<< *ite <<endl;



    //查看两个区间是否相等
    // cout<<equal(v.begin(),v.end(),v2.begin(),v2.end())<<endl;



        // vector<int> v ={2,3,4,5};
    
        // vector<int> v2 ={2,3,3};

        // auto pair = mismatch(v.begin(),v.end(),v2.begin(),v2.end());
        // cout<<*pair.first<<" "<< *pair.second<<endl;



        // string s1 = "hello";
        // string s2 = "hollo";



        // vector<int> v = {1,2,2,4,5,2,1};
        
        // // for_each(v.begin(), v.end(), [](int &a)
        // //          {a++;cout<<a<<" "; });
        // list<int> l;


        // l.resize(v.size());//先给链表扩容

        // copy(v.begin(),v.end(),l.begin());

        // for_each(l.begin(), l.end(), [](int &a)
        //           {cout<<a<<" "; });
        // cout<<endl;

        // vector<int> v = {1,2,2,4,5,2,1};
        // list<int> l;


        // l.resize(v.size());//先给链表扩容

        // copy_backward(v.begin(),v.end(),l.end());

        // for_each(l.begin(), l.end(), [](int &a)
        //           {cout<<a<<" "; });
        // cout<<endl;


        // vector<int> v = {1,2,3,4,5};
        // list<int> l;


        // l.resize(v.size());//先给链表扩容
        
        // //比copy多一个参数，就是在复制之前先进行一步 操作
        // transform(v.begin(),v.end(),l.begin(),[](int a){return a*2;});

        // for_each(l.begin(), l.end(), [](int &a)
        //           {cout<<a<<" "; });
        // cout<<endl;


        // 变动性算法一定要先扩容
        
        
        // vector<int> v2;

        // v2.resize(v.size()+l.size());
        
        // merge(v.begin(),v.end(),l.begin(),l.end(),v2.begin());  //使用之前最好先保证有序

        // for_each(v2.begin(), v2.end(), [](int &a)
        //             {cout<<a<<" "; });
        // cout<<endl;


        // swap_ranges(v.begin(),v.end(),l.begin());
        
        // for_each(v.begin(), v.end(), [](int &a)
        //             {cout<<a<<" "; });
        // cout<<endl;

        //数组用fill  链表用 fill_n
        //可以给各种容器赋处初值
        // fill(v.begin(),v.end(),0);
        // //给 几个 元素 赋初值
        // fill_n(v.begin(),3,0);


        // int a = 0;
        // generate(v.begin(),v.end(),[&a](){return ++a;});
        
        // for_each(v.begin(), v.end(), [](int &a)
        //              {cout<<a<<" "; });
        // cout<<endl;



        // vector<int> v = {1,1,2,3,4,5};
        
        // vector<int> v2;
        // v2.resize(v.size());
        // // replace(v.begin(),v.end(),1,99);

        // //原容器不动，把旧元素改成新元素，但是放到新的容器里
        // replace_copy(v.begin(),v.end(),v2.begin(),1,99);

        //  for_each(v.begin(), v.end(), [](int &a)
        //               {cout<<a<<" "; });
        //  cout<<endl;
        

        // for_each(v2.begin(), v2.end(), [](int &a)
        //               {cout<<a<<" "; });
        //  cout<<endl;
            

        // replace_if(v.begin(),v.end(),[](int &a){return a<4;},99);





        // vector<int> v={1,2,3,4,5};
        
        // remove(v.begin(),v.end(),3);
        
        // for_each(v.begin(),v.end(),[](int &a){cout << a<< " ";});
        // cout<<endl;





        











        //变序性算法

        // vector<int> v = {1,2,3,4,5};

        // reverse(v.begin(),v.end());

        // for_each(v.begin(),v.end(),[](int&a){cout<<a<<" ";});

        // cout<<endl;
        // cout<<v.size()<<endl;





            // 旋转
        // rotate(v.begin(),v.begin()+2,v.end());


        // 全排列  ：一个数列从小到大  从大到小的全部可能情况
        
        // 123 : 123的上一个是321
        // 132
        // 213
        // 231
        // 312
        // 321


        // next_permutation()
        // prev_permutation()


        // srand(time(nullptr));
        // random_shuffle(v.begin(),v.end());

        // for_each(v.begin(),v.end(),[](int&a){cout<<a<<" ";});

        // cout<<endl;



        //不稳定 分组
        // partition(v.begin(),v.end(),[](int a){return a%2==0 ;});

        // for_each(v.begin(),v.end(),[](int&a){cout<<a<<" ";});
        // cout<<endl;

        //稳定  stable

        // stable_partition(v.begin(),v.end(),[](int a){return a%2==0 ;});

        // for_each(v.begin(),v.end(),[](int&a){cout<<a<<" ";});
        // cout<<endl;










        // 排序性算法
        
        //标准库的排序：gcc编译器自己定的 是 16 其他编译器不一定
        
        // size <16 : 直接使用插入排序
        // size > 16 递归深度 为 0  使用堆排序
        // size > 16 递归深度 不为 0 快速排序
          
        // vector<int> v = {1,2,3,4,5};
        
        // sort(v.begin(),v.end(),std::greater<int>()); 
        
        // //如果不加比较器，默认是less 从小到大排
        
        // for_each(v.begin(),v.end(),[](int&a){cout<<a<<" ";});
        
        // cout<<endl;
        
        //稳定的排序  ：注意 这 个 size 也是gcc 编译器自己定的
        //size < 15 直接用插入排序
        // size > 15 直接分组  然后分别插入  用归并排序 ，全都是稳定的

        // stable_sort(v.begin(),v.end());
        // for_each(v.begin(),v.end(),[](int&a){cout<<a<<" ";});
        // cout<<endl;




        // vector<int> v = {5,1,4,2,3};

        // partial_sort(v.begin(),v.begin()+2,v.end());

        // for_each(v.begin(),v.end(),[](int&a){cout<<a<<" ";});
        // cout<<endl;


        //只排第 n 个元素  ： 也是用的 堆排 逻辑
        // vector<int> v = {99,8,3,1,4,2,0};
        // nth_element(v.begin(),v.begin(),v.end());
        // for_each(v.begin(),v.end(),[](int&a){cout<<a<<" ";});
        // cout<<endl;


        // vector<int> v = {99,8,3,1,4,2,0};
        // make_heap(v.begin(),v.end(),std::greater<int>());
        
        // //默认的 比较器 是less  构建一个最大堆
        // // 如果想要构建最小堆 要用 greater 
        // v.push_back(12);
        // push_heap(v.begin(),v.end());//保证是一个堆
        // //插入之后再构建堆


        // pop_heap(v.begin(),v.end());//从堆里弹出根，放到最后



        // sort_heap(v.begin(),v.end());//只能对堆使用，排完之后不再是堆
        // for_each(v.begin(),v.end(),[](int&a){cout<<a<<" ";});
        // cout<<endl;



        
        // 已序区间算法

        // vector<int> v ={1,2,3,4,5};
        // cout<<binary_search(v.begin(),v.end(),2)<<endl;
        // 返回值 bool 类型  判断有没有这个值


        vector<int> v ={1,2,3,4,5};
        vector<int> v2 ={1,2};
        
        // cout<<includes(v.begin(),v.end(),v2.begin(),v2.end())<<endl;
        //判断 后一个容器 是否 是前一个  容器 的 子集
        //注意：必须是两个有序的

        //大于等于  输入参数第一个元素
        cout<<*lower_bound(v.begin(),v.end(),2)<<endl;
        
        //大于 输入参数的第一个元素
        cout<<*upper_bound(v.begin(),v.end(),2)<<endl;


        auto pair = equal_range(v.begin(),v.end(),2);
        //返回值 是一个区间
        cout<<distance(pair.first,pair.second)<<endl;

        //可以用来找 最大连续 元素区间



        














    return 0;
}